当前位置: 开发笔记 > 编程语言 > 正文

方阵|回路_HDU2859Phalanx(动态规划/哈希表)

作者：手机用户2502856053 | 来源：互联网 | 2024-10-09 15:39

篇首语：本文由编程笔记#小编为大家整理，主要介绍了HDU-2859Phalanx(动态规划/哈希表)相关的知识，希望对你有一定的参考价值。题目链接：点

篇首语：本文由编程笔记#小编为大家整理，主要介绍了HDU - 2859 Phalanx(动态规划/哈希表)相关的知识，希望对你有一定的参考价值。

题目链接&＃xff1a;点击查看

题目大意&＃xff1a;给定一个整数n&＃xff0c;然后给出一个n*n的方阵&＃xff0c;求方阵中最大的对称子方阵&＃xff08;对称指的是以右上角至左下角为对角线&＃xff09;

分析&＃xff1a;这个题网上有个一般做法&＃xff0c;相当于一个动态规划的小模拟&＃xff0c;时间复杂度为&＃xff0c;这里不再赘述&＃xff0c;一会直接上代码。

然后还有一个方法&＃xff0c;是那天讲题的时候&＃xff0c;鑫爷以非同常人的脑回路提出的&＃xff0c;可以先用打一个哈希表&＃xff0c;然后再遍历每一个点进行

判断&＃xff0c;如果判断相等则直接更新&＃xff0c;如果不相等则可以二分查找最长的相等子序列&＃xff0c;这样时间复杂度就下降到了logn了&＃xff0c;提交的

时候比一般方法快了十倍还多&＃xff0c;不得感叹真的tql。

直接上代码吧&＃xff1a;

一般做法&＃xff1a;

#include<iostream> #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int inf&＃61;0x3f3f3f3f; const int N&＃61;1e3&＃43;100; char maze[N][N]; int dp[N][N]; int main() // freopen("input.txt","r",stdin); int n; while(scanf("%d",&n)!&＃61;EOF&&n) for(int i&＃61;0;i scanf("%s",maze&＃43;i); fill(dp[0],dp[0]&＃43;N*N,1); int ans&＃61;1; for(int i&＃61;1;i for(int j&＃61;0;j int x&＃61;i; int y&＃61;j; while(maze[x][j]&＃61;&＃61;maze[i][y]) x--; y&＃43;&＃43;; if(x<0||y>&＃61;n) break; x&＃61;i-x;//所记录的最长相等子序列的长度 if(x>dp[i-1][j&＃43;1]) dp[i][j]&＃61;dp[i-1][j&＃43;1]&＃43;1; else dp[i][j]&＃61;x; ans&＃61;max(dp[i][j],ans); cout< return 0;
哈希表&＃43;二分&＃xff1a;

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef unsigned long long ULL; const int inf&＃61;0x3f3f3f3f; const int N&＃61;1e3&＃43;100; ULL p[N],hash_1[N][N],hash_2[N][N]; char maze[N][N]; int dp[N][N]; void hash_(int n) for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;) hash_1[i][j]&＃61;hash_1[i][j-1]*131&＃43;(maze[i][j]-&＃39;a&＃39;&＃43;1); for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;) for(int i&＃61;n;i>&＃61;1;i--) hash_2[i][j]&＃61;hash_2[i&＃43;1][j]*131&＃43;(maze[i][j]-&＃39;a&＃39;&＃43;1); void initp() p[0]&＃61;1; for(int i&＃61;1;i p[i]&＃61;p[i-1]*131; void init(int n) memset(maze,0,sizeof(maze)); for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;) dp[i][j]&＃61;1; memset(hash_1,0,sizeof(hash_1)); memset(hash_2,0,sizeof(hash_2)); int main() // freopen("input.txt","r",stdin); int n; initp(); while(scanf("%d",&n)!&＃61;EOF&&n) init(n); for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%s",maze[i]&＃43;1); hash_(n); int mmax&＃61;1; for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;) for(int j&＃61;n-1;j>&＃61;1;j--) int k&＃61;dp[i-1][j&＃43;1]; ULL a&＃61;hash_1[i][j&＃43;k]-hash_1[i][j-1]*p[k&＃43;1]; ULL b&＃61;hash_2[i-k][j]-hash_2[i&＃43;1][j]*p[k&＃43;1]; if(a&＃61;&＃61;b) dp[i][j]&＃61;k&＃43;1; else int l&＃61;1,r&＃61;k; int ans&＃61;0; while(l<&＃61;r) int mid&＃61;(l&＃43;r)/2; ULL a&＃61;hash_1[i][j&＃43;mid]-hash_1[i][j-1]*p[mid&＃43;1]; ULL b&＃61;hash_2[i-mid][j]-hash_2[i&＃43;1][j]*p[mid&＃43;1]; if(a&＃61;&＃61;b) ans&＃61;mid; l&＃61;mid&＃43;1; else r&＃61;mid-1; dp[i][j]&＃61;ans&＃43;1; mmax&＃61;max(mmax,dp[i][j]); cout< return 0;

推荐阅读

function
字符串中特定字符的移除方法

本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符，并提供了多种编程语言的实现示例。 ... [详细]

蜡笔小新 2024-12-22 00:08:06
function
使用栈实现字符串中括号匹配的C++程序

本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现，并详细解释了算法的核心思想和具体实现步骤。 ... [详细]

蜡笔小新 2024-12-22 11:44:35
buffer
优化C++项目中的JSON处理：选择高性能的RapidJSON库

在高并发需求的C++项目中，我们最初选择了JsonCpp进行JSON解析和序列化。然而，在处理大数据量时，JsonCpp频繁抛出异常，尤其是在多线程环境下问题更为突出。通过分析发现，旧版本的JsonCpp存在多线程安全性和性能瓶颈。经过评估，我们最终选择了RapidJSON作为替代方案，并实现了显著的性能提升。 ... [详细]

蜡笔小新 2024-12-21 18:13:59
hash
深入解析Spring启动过程

本文详细介绍了Spring框架的启动流程，帮助开发者理解其内部机制。通过具体示例和代码片段，解释了Bean定义、工厂类、读取器以及条件评估等关键概念，使读者能够更全面地掌握Spring的初始化过程。 ... [详细]

蜡笔小新 2024-12-21 17:33:44
php
解决C# Windows Forms客户端连接SignalR服务器时出现的错误

在尝试使用C# Windows Forms客户端通过SignalR连接到ASP.NET服务器时，遇到了内部服务器错误（500）。本文将详细探讨问题的原因及解决方案。 ... [详细]

蜡笔小新 2024-12-21 16:55:52
process
Issue with @name Annotation in Documentation Generation

This post discusses an issue encountered while using the @name annotation in documentation generation, specifically regarding nested class processing and unexpected output. ... [详细]

蜡笔小新 2024-12-21 13:50:08
process
HDU5444：暴力求解策略

本文介绍了如何使用暴力方法解决HDU5444问题。代码通过逐个检查输入数据，确保在所有情况下都能找到正确的解决方案。 ... [详细]

蜡笔小新 2024-12-21 13:05:28
hash
并发编程 12—— 任务取消与关闭之 shutdownNow 的局限性

Java并发编程实践目录并发编程01——ThreadLocal并发编程02——ConcurrentHashMap并发编程03——阻塞队列和生产者-消费者模式并发编程04——闭锁Co ... [详细]

蜡笔小新 2024-12-21 12:39:07
function
使用Fetch进行HTTP请求的基本示例

本文介绍了如何使用JavaScript的Fetch API与Express服务器进行交互，涵盖了GET、POST、PUT和DELETE请求的实现，并展示了如何处理JSON响应。 ... [详细]

蜡笔小新 2024-12-22 12:55:37
数组
深入解析ArrayList与LinkedList的差异

本文详细对比了Java中ArrayList和LinkedList两种常用集合类的特性、性能及适用场景，通过代码示例进行测试，并结合实际应用场景分析其优缺点。 ... [详细]

蜡笔小新 2024-12-21 14:10:46
数组
深入探讨C++中移动赋值后析构函数的调用机制

本文详细解释了为什么在成功执行移动赋值操作后，对象的析构函数会被调用，并提供了代码示例和详细的分析。 ... [详细]

蜡笔小新 2024-12-21 14:09:38
数组
Java 中 LocalTime 类的 isSupported() 方法详解及示例

本文深入探讨了 Java 中 LocalTime 类的 isSupported() 方法，包括其功能、语法和使用示例。通过具体的代码片段，帮助读者理解如何检查特定的时间字段或单位是否被 LocalTime 类支持。 ... [详细]

蜡笔小新 2024-12-21 13:49:39
buffer
深入理解Java设计模式：装饰者模式

本文详细介绍了装饰者（Decorator）模式，这是一种动态地为对象添加职责的方法。与传统的继承方式不同，装饰者模式通过组合而非继承来实现功能扩展，从而提供更大的灵活性和可维护性。 ... [详细]

蜡笔小新 2024-12-21 13:38:07
buffer
初探七牛云存储：实现多服务器图片共享

为了解决不同服务器间共享图片的需求，我们最初考虑建立一个FTP图片服务器。然而，考虑到项目是一个简单的CMS系统，为了简化流程，团队决定探索七牛云存储的解决方案。本文将详细介绍使用七牛云存储的过程和心得。 ... [详细]

蜡笔小新 2024-12-21 13:15:50
hash
由二叉树到贪心算法

二叉树很重要树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。单就面试而言，在 ... [详细]

蜡笔小新 2024-12-21 13:13:13

手机用户2502856053

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章